//
// Created by Poyyo on 2021/5/25.
// 12.3 深度优先搜索
// 使用邻接表数据解结构
//

#include "Graph/GraphInMatrixImpl.h"
#include <stack>

using namespace std;

/**
 * 存储访问顺序栈
 */
stack<int> visitStack;

/**
 * 将当前访问的结点入栈
 * 访问栈顶元素
 * 从当前访问的顶点top移动到next时，将next入栈，如果top没有next，则删除top
 * @param graph
 * @param stack
 * @param id
 */
void dfs_fun(GraphInMatrixImpl &graph, stack<int> &stack, int id) {
    // 将id压栈
    stack.push(id);
    // 标记id已经入栈
    graph.Select(id);
    // 当栈飞控
    while (!stack.empty()) {
        // 获取栈顶元素
        auto visitId = stack.top();
        // 获取与id有连接的所有结点
        auto nextVs = graph.GetLinkedVertexes(visitId);
        // 标记是否存在还没访问的与id相邻的结点
        auto flag = false;
        // 遍历id的邻接结点
        for (auto item : nextVs) {
            // 如果存在结点未访问，压栈并结束循环
            if (!graph.getVertexes()[item].isSelected()) {
                stack.push(item);
                // 标记item已经入栈
                graph.Select(item);
                flag = true;
                break;
            }
        }
        // 如果id邻接结点没有或者都被访问过，则访问id
        if (!flag) {
            stack.pop();
            visitStack.push(visitId);
        }
    }
}

/**
 * 图的深度优先遍历算法
 * 邻接表表示
 * @param graph
 */
void dfs(GraphInMatrixImpl& graph) {
    // 深度优先遍历栈
    stack<int> stack;
    // 遍历图的顶点
    auto &vertexes = graph.getVertexes();
    for (int i = 1; i < vertexes.size(); i++) {
        // 如果顶点没有被访问，则开启深度遍历
        if (!vertexes[i].isSelected()) {
            dfs_fun(graph, stack, i);
        }
    }
    cout << endl;
}

void Read() {
    while (!visitStack.empty()) {
        cout << visitStack.top() << " ";
        visitStack.pop();
    }
}


/*
1 2 2 4
2 1 4
3 0
4 1 3
 */
int main() {
    GraphInMatrixImpl graphInMatrix;
    graphInMatrix.ToString();
    dfs(graphInMatrix);
    graphInMatrix.ToString();
    Read();
}